/**
 * describe:
 *
 * @author chaP
 * @date 2019/01/17
 */
package CodingTest.AC20190117;

import java.util.*;


public class singleNumber {
    /** 暴力法：
     *
     *
     */
    public int singleNumber1(int[] nums){
           ArrayList<Integer> list = new ArrayList<Integer>();
           for(int i = 0;i<nums.length;i++){
               if(!list.contains(nums[i]))
                   list.add(nums[i]);
               else
                   list.remove(new Integer(nums[i])); //remove装箱 如果不装箱的话remove删除的是下标,list.remove(o)和list.remove(index)
           }
           return list.get(0);
    }

    /**
     *hashMap法
     *
     */

    public int singleNumber2(int[] nums){
        int result = 0;
        HashMap<Integer,Integer> map = new HashMap<Integer, Integer>();
        for(int i = 0; i<nums.length;i++){
            if(map.containsKey(nums[i])){
                map.put(nums[i],map.get(nums[i])+1);

            }else{
                map.put(nums[i],1);
            }

        }
        for(int j = 0; j<nums.length;j++){
            if(map.get(nums[j])==1){
                result = nums[j];
                break;
            }

        }
        return result;

    }

    /**
     *异或法
     *java的位运算符中有一个叫异或的运算符，用符号(^)表示，其运算规则是：两个操作数的位中，相同则结果为0，不同则结果为1。
     * 分析上面程序，i=15转成二进制是1111，j=2转成二进制是0010，根据异或的运算规则得到的是1101，转成十进制就是13.
     * 利用这个规则我们可以灵活运用到某些算法。比如，假定有2K+1个数，其中有2k个相同，需要找出不相同的那个数，比如：2、3、4、4、3、5、6、6、5。

     */
    public int singleNumber3(int[] nums){
        int v = 0;
        for(int i = 0;i<nums.length;i++){
            v ^= nums[i];
        }
        return v;
    }
    public static void main(String[] args){
        int[] nums = {4,1,2,1,2};
        singleNumber sl = new singleNumber();
        int result = sl.singleNumber3(nums);
        System.out.println(result);
    }
}
